In continuously operating, real-time operating systems, such as the operating systems in telephone switching systems, data allocation and retrieval efficiency of the database are critical. A telephone switching system may make several database queries for a telephone call routed through the system. Therefore, advanced techniques must be used to ensure that data can be read and changed in the most efficient manner possible.
"Hashing" is used in many database storage and retrieval systems in order to increase efficiency. A hashing system numerically processes one or more data items in key fields and uses the "hashed" key as an index into a memory location for storage or retrieval of data. This is a savings in memory space over systems that use a key an a direct index, because there is much wasted space in an indexed system for those memory locations that do not have any data. A hashed database stores data more densely by using a hashing algorithm that distributes keys relatively evenly over the memory spectrum.
A hashing system, however, is only as efficient as its handling of "collisions"; which occurred when a plurality of different data items hash to the same memory location. Some prior art systems use the next sequential memory location to store data when there is a collision. This technique causes further collisions when data hashes to that location. Other prior art systems have one or more "overflow" areas where collision data is stored in one long list. This technique is very costly because linear list searching is very slow.
Therefore, a problem in the art is that there is no system for efficiently handling collisions in hashing database systems.